package a3_p04_jw_kw.spanningtree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

import org.jgrapht.Graph;
import org.jgrapht.Graphs;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.util.FibonacciHeap;
import org.jgrapht.util.FibonacciHeapNode;

import a1_p04_jw_kw.graph.GraphCreater;
import a1_p04_jw_kw.graph.GraphUtility;
import a1_p04_jw_kw.struct.GraphSetup;
import a1_p04_jw_kw.struct.GraphStatistic;
import a1_p04_jw_kw.struct.GraphTransition;
import a1_p04_jw_kw.struct.Node;
import a3_p04_jw_kw.comparator.NodeComparator;

public class PrimFibonacciJGraphT {
	Graph<Node,DefaultWeightedEdge> g;
	Graph<Node,DefaultWeightedEdge> spanningTree;
	
	HashMap<Node,Node> parents = new HashMap<Node,Node>();
	HashMap<Node,Set<DefaultWeightedEdge>> neighbors = new HashMap<Node,Set<DefaultWeightedEdge>>();
	
	HashMap<Node,FibonacciHeapNode<Node>> mapping = new HashMap<Node,FibonacciHeapNode<Node>>();	
	
	final private static Double INFINITE = 99999999.0;
	
	GraphStatistic stats = new GraphStatistic();
	
	FibonacciHeap<Node> q;
	
	long clock;	
	
	Node start;
	
	public PrimFibonacciJGraphT(Graph<Node,DefaultWeightedEdge> g, String start) {
		this.g = g;
		this.start = GraphUtility.getNode(this.g, start);
		
	}
	
	public void createSpanningTree() {
		startWatch();
		
		//initialize
		
		//create priority queue
		this.q = new FibonacciHeap<Node>();		
		
		for (Node u: this.g.vertexSet()) {
			//u.attribute = INFINITE;
			this.parents.put(u, null); //set all partens to null
			//this.neighbors.put(u, Graphs.neighborListOf(this.g, u));
			this.neighbors.put(u, this.g.edgesOf(u));
			FibonacciHeapNode<Node> heapnode = new FibonacciHeapNode<Node>(u);
			
			//this.q.insert(u, INFINITE);
			if (u.equals(start)) {
				this.q.insert(heapnode, 0.0);
				
			} else {
				this.q.insert(heapnode, (double)INFINITE);
				
			}
			
			u.attribute = INFINITE;
			
			this.mapping.put(u, heapnode);
			
		}		
		
		start.attribute = 0;
		
		while (!this.q.isEmpty()) {
//			for (Node n : this.q) {
//				System.out.print(n + ":" + n.attribute + " ");
//			}
			
			//Entry<Node,Double> entry = this.q.getMinimum();
			//Node nextNode = entry.getKey(); //get the lowest valued key from the queue
//			System.out.println(this.q.toString());
			
			
			FibonacciHeapNode<Node> fhn = this.q.min();
			
//			System.out.println(this.q.toString());
			Node nextNode = fhn.getData();
//			System.out.println("checking node: " + nextNode + " value: " + fhn.getKey());
						
			for (DefaultWeightedEdge e : this.neighbors.get(nextNode)) {
				double edgeWeight = this.g.getEdgeWeight(e);
				//if v isnt inspected and edgeweight from nextNode to v is smaller then current distance of v
				Node target = this.g.getEdgeTarget(e);
				if (target.equals(nextNode)) {
					target = this.g.getEdgeSource(e);
					
				}
				
				//System.out.println("inspecting: " + target);
				
				if ((this.mapping.keySet().contains(target)) && (edgeWeight < target.attribute)) {
					
					this.parents.put(target, nextNode);
					target.attribute = edgeWeight;
					this.q.decreaseKey(mapping.get(target), edgeWeight);
					
//					System.out.println("node: " + target.name + " " + edgeWeight);
					
					//this.q.decreaseKey(entry, target);
					//System.out.println("add node: " + nextNode + " to node: " + target + " as parent");
				}
			}
			
			//this.q.removeMin();
			this.q.delete(fhn);			
			
			
			this.mapping.remove(nextNode);
		}	
		
		stopWatch();		
		
		//creates the spanning tree
		createGraph();
	}
	
	//returns the sum of all edge weights
	public double getEdgeWeightSum() {
		double sum = 0.0;
		for (DefaultWeightedEdge e : this.spanningTree.edgeSet()) {
			sum = sum + this.spanningTree.getEdgeWeight(e);
			
		}
		
		
		return sum;
	}
	
	public void createGraph() {
		ArrayList<GraphTransition> transitions = new ArrayList<GraphTransition>();
		
		for (Node n : this.g.vertexSet()) {
			if (!(this.parents.get(n) == null)) { 
				transitions.add(new GraphTransition(n, this.parents.get(n), String.valueOf(this.g.getEdgeWeight(this.g.getEdge(n, this.parents.get(n))))));
			}
		}
		
		GraphSetup gs = new GraphSetup(false, true, false, true, transitions);
		GraphCreater gc = new GraphCreater(gs);
		gc.createGraph();
		
		this.spanningTree = gc.getGraph();
	}
	
	
	public Graph<Node,DefaultWeightedEdge> getSpanningTree() {
		return this.spanningTree;
		
	}
	
	public GraphStatistic getStatistic() {
		return this.stats;
		
	}
	
	private void startWatch() {
		this.clock = System.currentTimeMillis();
		
	}
	
	private void stopWatch() {
		long stop = System.currentTimeMillis();
		stats.time = stats.time + (stop - clock);
		
	}	

}
